package com.javaDemo.ti;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @ClassName: BucketSort
 * @Auther: csy
 * @Date: 2022/2/10 17:49
 * @Description:
 */
public class BucketSort {
    public static void main(String[] args) {
        int[] a = new int[]{4, 8, 5, 9, 0, 2, 1, 7};
        bucketSorts(a);
        System.out.println();
    }

    public static void bucketSorts(int[] arr) {
        // 计算最大值与最小值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }

        // 计算桶的数量
        int bucketNum = (max - min) / arr.length + 1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
        for (int i = 0; i < bucketNum; i++) {
            bucketArr.add(new ArrayList<Integer>());
        }

        // 将每个元素放入桶
        for (int i = 0; i < arr.length; i++) {
            int num = (arr[i] - min) / (arr.length);
            bucketArr.get(num).add(arr[i]);
        }

        // 对每个桶进行排序
        for (int i = 0; i < bucketArr.size(); i++) {
            Collections.sort(bucketArr.get(i));
        }

        // 将桶中的元素赋值到原序列
        int index = 0;
        for (int i = 0; i < bucketArr.size(); i++) {
            for (int j = 0; j < bucketArr.get(i).size(); j++) {
                arr[index++] = bucketArr.get(i).get(j);
            }
        }
    }


    private static void bucketSort(int[] nums) {
        int INTERVAL = 100;               // 定义桶的大小
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int num : nums) {            // 找到数组元素的范围
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        int count = (max - min + 1);      // 计算出桶的数量
        int bucketSize = (count % INTERVAL == 0) ? (count / INTERVAL) : (count / INTERVAL + 1);
        List<Integer>[] buckets = new List[bucketSize];
        for (int num : nums) {            // 把所有元素放入对应的桶里面
            int quotient = (num - min) / INTERVAL;
            if (buckets[quotient] == null) buckets[quotient] = new ArrayList<>();
            buckets[quotient].add(num);
        }
        int cur = 0;
        for (List<Integer> bucket : buckets) {
            if (bucket != null) {
                bucket.sort(null);       // 对每个桶进行排序
                for (Integer integer : bucket) {  // 还原桶里面的元素到原数组
                    nums[cur++] = integer;
                }
            }
        }
    }

}
